# LeetCode 778. 水位上升的泳池中游泳
# https://leetcode.cn/problems/swim-in-rising-water/description/?languageTags=python3
import heapq
from math import inf
from typing import List

# 复杂的解决办法1.。。
class Solution1:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        adj = {grid[i][j]: [] for i in range(n) for j in range(n)}
        for i in range(n):
            for j in range(n):
                if i + 1 < n:
                    adj[grid[i][j]].append(grid[i + 1][j])
                    adj[grid[i + 1][j]].append(grid[i][j])
                if j + 1 < n:
                    adj[grid[i][j]].append(grid[i][j + 1])
                    adj[grid[i][j + 1]].append(grid[i][j])

        def dijkstra(s, t):
            distance = {grid[i][j]: grid[i][j] for i in range(n) for j in range(n)}
            q = [(distance[s], s)]
            visited = set()
            while q:
                du, u = heapq.heappop(q)
                if u == t:
                    return du
                if du > distance[u]:
                    continue
                if u in visited:
                    continue
                visited.add(u)
                for v in adj[u]:
                    distance[v] = max(du, distance[v])
                    heapq.heappush(q, (distance[v], v))

        result = dijkstra(grid[0][0], grid[n - 1][n - 1])
        return result


# 更绕的解决办法2.。。
class Solution2:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        adj = {grid[i][j]: [] for i in range(n) for j in range(n)}
        for i in range(n):
            for j in range(n):
                if i + 1 < n:
                    adj[grid[i][j]].append(grid[i + 1][j])
                    adj[grid[i + 1][j]].append(grid[i][j])
                if j + 1 < n:
                    adj[grid[i][j]].append(grid[i][j + 1])
                    adj[grid[i][j + 1]].append(grid[i][j])
        nums = {grid[i][j]: grid[i][j] for i in range(n) for j in range(n)}

        def dijkstra(s, t):
            distance = {grid[i][j]: inf for i in range(n) for j in range(n)}
            distance[s] = nums[s]
            q = [(distance[s], s)]
            visited = set()
            while q:
                du, u = heapq.heappop(q)
                if u == t:
                    return du
                if du > distance[u]:
                    continue
                if u in visited:
                    continue
                visited.add(u)
                for v in adj[u]:
                    if v in visited:
                        continue
                    around = []
                    visited_around = []
                    for x in adj[v]:
                        if x in visited:
                            visited_around.append(nums[x] if distance[x] == inf else distance[x])
                        else:
                            around.append(nums[x] if distance[x] == inf else distance[x])
                    if not around:
                        continue
                    visited_around_min_value = 0
                    if visited_around:
                        visited_around_min_value = min(visited_around)
                    min_value = min(around)
                    if visited_around_min_value >= nums[v]:
                        distance[v] = visited_around_min_value
                        heapq.heappush(q, (distance[v], v))
                    elif min_value >= nums[v]:
                        distance[v] = min_value if v != t else nums[v]
                        heapq.heappush(q, (distance[v], v))
                    else:
                        if distance[v] == inf:
                            distance[v] = nums[v]
                            heapq.heappush(q, (distance[v], v))

        result = dijkstra(grid[0][0], grid[n - 1][n - 1])
        return result


# 简单一点的解决办法3.。。
class Solution3:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        adj = {(i, j): [] for i in range(n) for j in range(n)}
        edge_length = {(i, j): {} for i in range(n) for j in range(n)}
        for i in range(n):
            for j in range(n):
                if i + 1 < n:
                    adj[(i, j)].append((i + 1, j))
                    edge_length[(i, j)][(i + 1, j)] = grid[i + 1][j]
                if i - 1 >= 0:
                    adj[(i, j)].append((i - 1, j))
                    edge_length[(i, j)][(i - 1, j)] = grid[i - 1][j]
                if j + 1 < n:
                    adj[(i, j)].append((i, j + 1))
                    edge_length[(i, j)][(i, j + 1)] = grid[i][j + 1]
                if j - 1 >= 0:
                    adj[(i, j)].append((i, j - 1))
                    edge_length[(i, j)][(i, j - 1)] = grid[i][j - 1]


        def dijkstra(s, t):
            result = 0
            distance = {(i, j): grid[i][j] for i in range(n) for j in range(n)}
            q = [(distance[s], s)]
            visited = set()
            while q:
                du, u = heapq.heappop(q)
                if du > result:
                    result = du
                if u == t:
                    return result
                if du > distance[u]:
                    continue
                if u in visited:
                    continue
                visited.add(u)

                for v in adj[u]:
                    # alt = du + edge_length[u][v]
                    if v in visited:
                        continue
                    heapq.heappush(q, (distance[v], v))
            return result

        result = dijkstra((0, 0), (n - 1, n - 1))
        return result


# 按照 DIJKSTRA 模板
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        adj = {grid[i][j]: [] for i in range(n) for j in range(n)}
        for i in range(n):
            for j in range(n):
                if i + 1 < n:
                    adj[grid[i][j]].append(grid[i + 1][j])
                if i - 1 >= 0:
                    adj[grid[i][j]].append(grid[i - 1][j])
                if j + 1 < n:
                    adj[grid[i][j]].append(grid[i][j + 1])
                if j - 1 >= 0:
                    adj[grid[i][j]].append(grid[i][j - 1])


        def dijkstra(s, t):
            distance = {grid[i][j]: inf for i in range(n) for j in range(n)}
            distance[s] = s
            q = [(distance[s], s)]
            while q:
                du, u = heapq.heappop(q)
                if u == t:
                    return du
                if du > distance[u]:
                    continue

                for v in adj[u]:
                    alt = max(du, v)
                    if alt < distance[v]:
                        distance[v] = alt
                        heapq.heappush(q, (distance[v], v))

        result = dijkstra(grid[0][0], grid[n - 1][n - 1])
        return result


if __name__ == '__main__':
    grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
    # grid = [[3,2],[0,1]]
    # grid = [[0, 3], [1, 2]]
    # grid = [[10,12,4,6],[9,11,3,5],[1,7,13,8],[2,0,15,14]]
    # grid = [[0, 2], [1, 3]]
    # print(Solution3().swimInWater(grid))
    print(Solution().swimInWater(grid))
